import java.util.*;

public class 岛屿数量 {
    //https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=295&tqId=1024684&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    //简单的bfs复习题了
    int m;
    int n;
    boolean[][] vis;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int solve (char[][] grid) {
        // write code here
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m];
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(grid[i][j] == '1' && !vis[i][j]){
                    vis[i][j] = true;
                    bfs(i,j,grid);
                    count++;
                }
            }
        }
        return count;
    }
    public void bfs(int i,int j,char[][] grid){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j});
        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0];
            int b = t[1];
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1' && !vis[x][y]){
                    q.add(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }
    }
}
